import heapq

def dijkstra(graph, start):
    n = len(graph)
    distance = [float('inf')] * len(graph)
    distance[start] = 0
    visited = [False] * n

    heap = [(0, start)]
    while heap:
        cost, u = heapq.heappop(heap)
        if not visited[u]:
            visited[u] = True
            for v, w in graph[u]:
                if not visited[v] and cost + w < distance[v]:
                    distance[v] = cost + w
                    heapq.heappush(heap, (distance[v], v))
    return distance


# 示例图的邻接表表示
graph = [
    [(1, 2), (2, 6), (3, 20)],
    [(0, 8), (2, 1), (4, 100)],
    [(1, 5), (3, 2), (4, 12)],
    [(2, 7), (4, 4)],
    [],
]
start_node = 0
shortest_distances = dijkstra(graph, start_node)
print(f"从节点 {start_node} 到其他节点的最短距离: {shortest_distances}")
